package main.剑指OfferⅡ;

import java.util.*;

public class Day25_Day28 {
    public static void main(String[] args) {
        System.out.println("**************************Day25**************************");
        System.out.println("剑指OfferⅡ074.合并区间");
        System.out.println("剑指OfferⅡ075.数组相对排序");
        System.out.println("**************************Day26**************************");
        System.out.println("剑指OfferⅡ076.数组中的第 k 大的数字");
        System.out.println("剑指OfferⅡ077.链表排序");
        System.out.println("剑指OfferⅡ078.合并排序链表");
        System.out.println("**************************Day27**************************");
        System.out.println("剑指OfferⅡ079.所有子集");
        System.out.println("剑指OfferⅡ080.含有 k 个元素的组合");
        System.out.println("剑指OfferⅡ081.允许重复选择元素的组合");
        System.out.println("**************************Day28**************************");
        System.out.println("剑指OfferⅡ082.含有重复元素集合的组合");
        System.out.println("剑指OfferⅡ083.没有重复元素集合的全排列");
        System.out.println("剑指OfferⅡ084.含有重复元素集合的全排列");
    }
}

class Offer74{
    public int[][] merge(int[][] intervals) {
        List<int[]> list=new ArrayList<>();
        Arrays.sort(intervals, new Comparator<int[]>() {//首元素升序，次元素降序
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0]!=o2[0]) return o1[0]-o2[0];
                else return o2[1]-o1[1];
            }
        });
        int start=intervals[0][0],end=intervals[0][1];
        for (int i=1;i<intervals.length;i++){
            int[] curInter=intervals[i];
            if (curInter[0]>end){//无交集
                list.add(new int[]{start,end});//添加前一个区间
                start=curInter[0];
                end=curInter[1];
            }else if (curInter[0]<=end){//存在交集
                end=Math.max(end,curInter[1]);//扩大又边界
            }
        }
        list.add(new int[]{start,end});
        int[][] result=new int[list.size()][2];
        for (int i=0;i<list.size();i++){
            result[i][0]=list.get(i)[0];
            result[i][1]=list.get(i)[1];
        }
        return result;
    }
}

class Offer75{
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr1) {//记录每个元素出现次数
            if (map.containsKey(num)) map.put(num, map.get(num) + 1);
            else map.put(num, 1);
        }
        List<Integer> list = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        for (int num : arr2) {//按照 arr2 的排序填写 arr1
            int temp = map.get(num);
            for (int i = 0; i < temp; i++) list.add(num);
        }
        for (int num : arr1) {//将剩下的数加入到 list2 并排序
            if (!list.contains(num)) list2.add(num);
        }
        Collections.sort(list2);
        for (int num : list2) list.add(num);
        for (int i = 0; i < arr1.length; i++) arr1[i] = list.get(i);
        return arr1;
    }
}

class Offer76{
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}

class Offer77{
    public ListNode sortList(ListNode head) {
        List<Integer> list=new ArrayList<>();
        ListNode temp=head;
        while (temp!=null){
            list.add(temp.val);
            temp=temp.next;
        }
        Collections.sort(list);
        temp=head;
        for (int num:list){
            temp.val=num;
            temp=temp.next;
        }
        return head;
    }
}

class Offer78{
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode virtual=new ListNode();
        ListNode result=virtual;
        while (true){
            ListNode curMin=null;
            int minIndex=-1;
            for (int i=0;i< lists.length;i++){
                if (lists[i]==null) continue;
                if (curMin==null) {
                    curMin=lists[i];
                    minIndex=i;
                }
                else if (curMin!=null&&lists[i].val< curMin.val){//寻找到最小的节点，并记录该节点再数组中的位置
                    curMin=lists[i];
                    minIndex=i;
                }
            }
            if (minIndex!=-1) lists[minIndex]=lists[minIndex].next;//最小下标的链表向后移动
            if (curMin==null) break;
            result.next=curMin;//将最小的节点接入
            result=result.next;
        }
        return virtual.next;
    }
}

class Offer79{
    List<List<Integer>> list=new ArrayList<>();
    public void process(int[] nums,int start,List<Integer> curList){
        if (start>= nums.length){
            list.add(curList);
            return;
        }
        List<Integer> tempList=new ArrayList<>(curList);
        tempList.add(nums[start]);
        list.add(tempList);
        for (int i=start+1;i< nums.length;i++){
            process(nums,i,tempList);
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> tempList=new ArrayList<>();
        list.add(tempList);
        for (int i=0;i< nums.length;i++){//以i开始的所有子集
            process(nums,i,tempList);
        }
        return list;
    }
}

class Offer80{
    List<List<Integer>> list;
    int size,max;
    public void process(int start,List<Integer> last){
        List<Integer> cur=new ArrayList<>(last);
        if (cur.size()==size){//大小满足
            list.add(cur);
            return;
        }
        for (int i=start;i<=max;i++){
            cur.add(i);
            process(i+1,cur);
            cur.remove(cur.size()-1);
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        size=k;
        max=n;
        list=new ArrayList<>();
        List<Integer> temp=new ArrayList<>();
        for (int i=1;i<=n;i++){
            temp.add(i);
            process(i+1,temp);
            temp.remove(0);
        }
        return list;
    }
}

class Offer81{
    List<List<Integer>> list;
    int target;
    public void process(List<Integer> last,int[] candidates,int sum,int start){
        List<Integer> curList=new ArrayList<>(last);
        if (sum==target) {
            list.add(curList);
            return;
        }else if (sum>target) return;
        else {
            for (int i=start;i< candidates.length;i++){
                curList.add(candidates[i]);
                process(curList,candidates,sum+candidates[i],i);
                curList.remove(curList.size()-1);
            }
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> temp=new ArrayList<>();
        list=new ArrayList<>();
        this.target=target;
        for (int i=0;i< candidates.length;i++){
            temp.add(candidates[i]);
            process(temp,candidates,candidates[i],i);
            temp.remove(0);
        }
        return list;
    }
}

class Offer82{
    List<List<Integer>> lists = new ArrayList<>();
    Deque<Integer> deque = new LinkedList<>();
    int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        boolean[] flag = new boolean[candidates.length];
        backTracking(candidates, target, 0, flag);
        return lists;
    }

    public void backTracking(int[] arr, int target, int index, boolean[] flag) {
        if (sum == target) {
            lists.add(new ArrayList(deque));
            return;
        }
        for (int i = index; i < arr.length && arr[i] + sum <= target; i++) {
            if (i > 0 && arr[i] == arr[i - 1] && !flag[i - 1]) {//出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
                continue;
            }
            flag[i] = true;
            sum += arr[i];
            deque.push(arr[i]);
            backTracking(arr, target, i + 1, flag);//每个节点仅能选择一次，所以从下一位开始
            int temp = deque.pop();
            flag[i] = false;
            sum -= temp;
        }
    }
}

class Offer83{
    List<List<Integer>> list;
    boolean[] vis;
    public void process(List<Integer> last,int[] nums){
        List<Integer> curList=new ArrayList<>(last);
        if (curList.size()== nums.length){
            list.add(curList);
            return;
        }else {
            for (int i=0;i< nums.length;i++){
                if (!vis[i]){
                    curList.add(nums[i]);
                    vis[i]=true;
                    process(curList,nums);
                    curList.remove(curList.size()-1);
                    vis[i]=false;
                }
            }
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        list=new ArrayList<>();
        vis=new boolean[nums.length];
        List<Integer> temp=new ArrayList<>();
        for (int i=0;i<nums.length;i++){
            if (!vis[i]){
                temp.add(nums[i]);
                vis[i]=true;
                process(temp,nums);
                temp.remove(0);
                vis[i]=false;
            }
        }
        return list;
    }
}

class Offer84{
    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        process(nums, ans, 0, perm);
        return ans;
    }

    public void process(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) continue;
            perm.add(nums[i]);
            vis[i] = true;
            process(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }
}